﻿/*
题目: 交易的逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    /**
    * 需要注意边界情况，s1 >= s2 的时候才进行结算，否则会多算一些 s1 = s2 的情况
    */

    int res;

    int reversePairs(vector<int>& record) {
        res = 0;
        merge_sort(record, 0, record.size() - 1);
        return res;
    }

    void merge_sort(vector<int>& nums, int left, int right) {
        if (left >= right)  return;

        int mid = left + ((right - left) >> 1);
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    void merge(vector<int>& nums, int left, int mid, int right) {
        int s1 = left, s2 = mid + 1;
        int e1 = mid, e2 = right;

        vector<int> tmp(right - left + 1, 0);
        int k = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] <= nums[s2]) {
                res += (s2 - mid - 1);
                tmp[k++] = nums[s1++];
            }
            else {  // nums[s1] > nums[s2]
                tmp[k++] = nums[s2++];
            }
        }

        while (s1 <= e1) {
            res += (s2 - mid - 1);
            tmp[k++] = nums[s1++];
        }
        while (s2 <= e2)    tmp[k++] = nums[s2++];

        for (int i = 0; i < k; i++) {
            nums[left + i] = tmp[i];
        }
    }
};
